package _06_贪心;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        //价值主导的策略,大的放在前面
        select("价值主导",(a1,a2)->{
            return a2.value-a1.value;
        });

        //重量主导的策略,小的放在前面
        select("重量主导",(a1,a2)->{
            return a1.weight - a2.weight;
        });

        //价值密度主导的策略,小的放在前面
        select("价值密度主导",(a1,a2)->{
            return Double.compare(a2.ValueDensity,a1.ValueDensity);
        });
    }

    //按照比较器规则进行排序
    static void select(String title,Comparator<Article> cmp){
        //构造背包
        Article[] articles = new Article[] {
                new Article(35, 10), new Article(30, 40),
                new Article(60, 30), new Article(50, 50),
                new Article(40, 35), new Article(10, 40),
                new Article(25, 30)
        };
        //开始排序
        Arrays.sort(articles,cmp);

        int capacity = 150,weight = 0,value = 0; //背包容量为150,背包装了多重，总价值多少
        List<Article> selectArticles = new LinkedList<>();
        for (int i = 0; i < articles.length && weight<capacity; i++) { //开始装
            int newWeight = weight + articles[i].weight; //背包装一件物品后的容量
            if(newWeight <= capacity){ //装了之后的容量小于等于背包总容量
                weight = newWeight;//更新
                value += articles[i].value; //更新总价值
                selectArticles.add(articles[i]); //将这个物品加入数组
            }
        }
        System.out.println("["+title+"]");
        System.out.println("总价值:"+value);
        System.out.println("--------------------------");
        for (int i = 0; i < selectArticles.size(); i++) {
            System.out.println(selectArticles.get(i));
        }
        System.out.println("--------------------------");
    }
}
